package com.gxc.string;

/**
 * 字符串str1和str2，str1是否包含str2，如果包念，返回str2在str1中开始的位置
 * 如何做到时间复杂度0(N)完成?
 */
public class KMP {

    public static void main(String[] args) {
        String str1 = "";
        String str2 = "";

    }

    private static int kmp(char[] a, char[] b) {
        if (a.length<b.length || b.length<1) return -1;

        int[] nextarr = getNextArray(b);

        int i = 0;
        int j = 0;
        while (i<a.length && j<b.length) {
            //字符相等
            if (a[i] == b[j]) {
                i++;
                j++;
                //字符不相等，但前缀和后缀有相同的字符串，可加速
            } else if (nextarr[j]>-1){
                j = nextarr[j];
            } else {
                //字符不相等，且前缀和后缀无相同的字符串
                i++;
            }
        }
        //i或j越界了
        return j == b.length?i-j:-1;
    }

    /**
     * 字符串b的前缀和后缀相同的最长长度
     * @param b
     * @return
     */
    private static int[] getNextArray(char[] b) {
        if (b.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[b.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cm = 0;
        while (i<b.length) {
            if (b[i-1] == b[cm]) {
                next[i++] = ++cm;
            } else if (cm>0) {
                //当跳到cm的时候，和i-1的字符不匹配，可加速
                cm = next[cm];
            } else {
                next[i++]=0;
            }
        }
        /*  abbstabb ec abbstabb?
        for (; i < b.length; i++) {
            int isNeedAdd = 0;
            if (b[i-1] == b[next[i-1]]) {
                isNeedAdd = 1;
            }
            next[i] = next[i-1] + isNeedAdd;
        }*/
        return next;
    }
}
